package cn.hycat.leetcode.middle;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
/*
        记忆化搜索 -> 动态规划
        一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
        机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）
        问总共有多少条不同的路径？
*/
public class L62不同路径 {
    public static void main(String[] args) {
        System.out.println(uniquePaths2(7, 3));
    }

    //记忆化搜索版本  表示 走到i j位置的时候 有多少种方法
    public int dfs(int m, int n, int i, int j, int[][] dp) {
        if(dp[i][j] != 0) {
            return dp[i][j];
        }

        if(m - 1 == i && n - 1 == j) {
            return 1;
        }

        if(i == m - 1) {
            dp[i][j] = dfs(m, n, i, j+1, dp);
        } else if(j == n - 1) {
            dp[i][j] = dfs(m, n, i+1, j, dp);
        } else {
            dp[i][j] = dfs(m, n, i, j+1, dp) + dfs(m, n, i+1, j, dp);
        }
        return dp[i][j];
    }

    //动态规划版本
    public static int uniquePaths2(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 || j == 0) dp[i][j] = 1;
                else
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
